//<p>给你一个变量对数组 <code>equations</code> 和一个实数值数组 <code>values</code> 作为已知条件，其中 <code>equations[i] = [A<sub>i</sub>, B<sub>i</sub>]</code> 和 <code>values[i]</code> 共同表示等式 <code>A<sub>i</sub> / B<sub>i</sub> = values[i]</code> 。每个 <code>A<sub>i</sub></code> 或 <code>B<sub>i</sub></code> 是一个表示单个变量的字符串。</p>
//
//<p>另有一些以数组 <code>queries</code> 表示的问题，其中 <code>queries[j] = [C<sub>j</sub>, D<sub>j</sub>]</code> 表示第 <code>j</code> 个问题，请你根据已知条件找出 <code>C<sub>j</sub> / D<sub>j</sub> = ?</code> 的结果作为答案。</p>
//
//<p>返回 <strong>所有问题的答案</strong> 。如果存在某个无法确定的答案，则用 <code>-1.0</code> 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 <code>-1.0</code> 替代这个答案。</p>
//
//<p><strong>注意：</strong>输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。</p>
//
//<p><strong>注意：</strong>未在等式列表中出现的变量是未定义的，因此无法确定它们的答案。</p>
//
//<p>&nbsp;</p>
//
//<p><strong class="example">示例 1：</strong></p>
//
//<pre>
//<strong>输入：</strong>equations = [["a","b"},{"b","c"]], values = [2.0,3.0], queries = [["a","c"},{"b","a"},{"a","e"},{"a","a"},{"x","x"]]
//<strong>输出：</strong>[6.00000,0.50000,-1.00000,1.00000,-1.00000]
//<strong>解释：</strong>
//条件：<em>a / b = 2.0</em>, <em>b / c = 3.0</em>
//问题：<em>a / c = ?</em>, <em>b / a = ?</em>, <em>a / e = ?</em>, <em>a / a = ?</em>, <em>x / x = ?</em>
//结果：[6.0, 0.5, -1.0, 1.0, -1.0 ]
//注意：x 是未定义的 =&gt; -1.0</pre>
//
//<p><strong class="example">示例 2：</strong></p>
//
//<pre>
//<strong>输入：</strong>equations = [["a","b"},{"b","c"},{"bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"},{"c","b"},{"bc","cd"},{"cd","bc"]]
//<strong>输出：</strong>[3.75000,0.40000,5.00000,0.20000]
//</pre>
//
//<p><strong class="example">示例 3：</strong></p>
//
//<pre>
//<strong>输入：</strong>equations = [["a","b"]], values = [0.5], queries = [["a","b"},{"b","a"},{"a","c"},{"x","y"]]
//<strong>输出：</strong>[0.50000,2.00000,-1.00000,-1.00000]
//</pre>
//
//<p>&nbsp;</p>
//
//<p><strong>提示：</strong></p>
//
//<ul> 
// <li><code>1 &lt;= equations.length &lt;= 20</code></li> 
// <li><code>equations[i].length == 2</code></li> 
// <li><code>1 &lt;= A<sub>i</sub>.length, B<sub>i</sub>.length &lt;= 5</code></li> 
// <li><code>values.length == equations.length</code></li> 
// <li><code>0.0 &lt; values[i] &lt;= 20.0</code></li> 
// <li><code>1 &lt;= queries.length &lt;= 20</code></li> 
// <li><code>queries[i].length == 2</code></li> 
// <li><code>1 &lt;= C<sub>j</sub>.length, D<sub>j</sub>.length &lt;= 5</code></li> 
// <li><code>A<sub>i</sub>, B<sub>i</sub>, C<sub>j</sub>, D<sub>j</sub></code> 由小写英文字母与数字组成</li> 
//</ul>
//
//<div><li>👍 1098</li><li>👎 0</li></div>

#include <bits/stdc++.h>
using namespace std;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    unordered_map<string, string> root;

    string findRoot(string u) {
        if (!root.contains(u)) {
            root[u] = u;
        }
        if (root[u] == u) return root[u];
        return root[u] = findRoot(root[u]);
    }

    void connect(string u, string v) {
        string rootU = findRoot(u);
        string rootV = findRoot(v);
        if (rootU == rootV) return;
        root[rootU] = rootV;
    }

    bool is_connect(string u, string v) {
        return findRoot(u) == findRoot(v);
    }

public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values,
                                vector<vector<string>>& queries) {
        unordered_map<string, unordered_map<string, double>> g;
        unordered_set<string> x;
        for (int i = 0; i < equations.size(); ++i) {
            string a = equations[i][0], b = equations[i][1];
            x.insert(a);
            x.insert(b);
            g[a][b] = values[i];
            g[b][a] = 1.0 / values[i];
            connect(a, b);
        }
        vector<double> ans;
        function<bool(string, string, string, double)> dfs = [&
            ](string pre, string cur, string target, double res) -> bool {
                
            if (cur == target) {
                ans.push_back(res);
                return true;
            }
            for (auto& [next, v] : g[cur]) {
                if (next == pre) continue;
                // 遍历到了
                if (dfs(cur, next, target, res * g[cur][next])) return true;
            }
            return false;
        };
        for (auto& q : queries) {
            string a = q[0], b = q[1];
            if (!x.contains(a) || !x.contains(b) || !is_connect(a, b)) ans.push_back(-1.0);
            else dfs("", a, b, 1.0);
        }
        return ans;
    }
};

//leetcode submit region end(Prohibit modification and deletion)


int main() {
    Solution s;
    vector<vector<string>> data = {{"a", "b"}, {"b", "c"}};
    vector values = {2.0, 3.0};
    vector<vector<string>> queries = {{"a", "c"}, {"b", "a"}, {"a", "e"}, {"a", "a"}, {"x", "x"}};

    s.calcEquation(data, values, queries);
}
